package leetcode;

/**
 * Created by Ghost on 2014/11/22.
 */
public class Recover_Binary_Search_Tree {
    TreeNode first = null;
    TreeNode second = null;
    TreeNode pre = new TreeNode(Integer.MIN_VALUE);

    private void recoverByInterOrder(TreeNode root){
        if(root==null)
            return;
        recoverByInterOrder(root.left);
        if(first==null && pre.val>=root.val){
            first = pre;
        }
        if(first!=null && pre.val>=root.val){
            second = root;
        }

        pre = root;

        recoverByInterOrder(root.right);

    }
    public void recoverTree(TreeNode root) {
        recoverByInterOrder(root);
        int val = first.val;
        first.val = second.val;
        second.val = val;
    }
}
